#include "graph.h"
#include<queue>
#include<QDebug>
tp::tp(int x,int y,date z):cost(x),id(y),t(z)
{
}
int Graph::find(QString name)
{
    for(int i = 0;i<citys.size();i++)
    {
        if(citys[i].getname()==name)
            return i;
    }
    return -1;
}
Graph::Graph() {}
QVector<Tinfo *> Graph::findTinfo(QString bcity,QString lcity,bool type)
{
    QVector<Tinfo *>res;
    int index = find(bcity);
    if(index != -1)
    {
        city & tar = citys[index];
        return tar.findinfo(lcity,type);
    }
    return res;
}//找到起始城市和类型对应的所有Tinfo
bool Graph::addcity(QString name)
{
    int index = find(name);
        if(index != -1)return 0;
        city newcity(name);
        citys.push_back(newcity);
        return 1;
}//ok
bool Graph::addtfinfo(QString bcity,QString lcity,date bdate,date ldate,int money,bool type)
{
    //终点城市存在时才能添加
    int index = find(bcity);
    if(index == -1){/*在此输出错误信息*/return 0;}
    int ecity = find(lcity);
    if(ecity == -1){/*在此输出错误信息*/return 0;}
    city & tar = citys[index];
    tar.addinfo(&citys[ecity],bdate,ldate,money,type);//type表示航班还是列车
    return 1;
}
void Graph::editinfo(Tinfo *t ,date newbdate,date newldate,int newmoney)//通过res里的index获取要修改的信息
{
    t->b=newbdate;
    t->l=newldate;
    t->cost=newmoney;
}
bool Graph::deletecity(QString city)
{
     //在图中先删除城市
    int index = find(city);
    if(index == -1){/*不存在要删除的城市*/return 0;}
    citys.erase(citys.begin()+index);
    //在所有城市中的Tinfo中删除终点为city的路径
    for(int i =0 ;i<citys.size();i++)
    {
        citys[i].deleteTinfo(city,0);//飞机
        citys[i].deleteTinfo(city,1);//列车
    }
    return 1;
}
void Graph::change(QString oldcity,QString newcity)
{
    int index = find(oldcity);
    if(index == -1){/*不存在原有城市*/return;}
    citys[index].setname(newcity);
}
/*需要修改*/void Graph::deletetfinfo(Tinfo  * t)
{
    //删除对应信息
    if(t == nullptr){return;}
    t->f->deletetp(t);
    //通过起点城市删除这个指针
}
QVector<Tinfo * > Graph::solution1(bool type,QString b,QString l,int * ans,date * ans2)
{
    //cost【id】为id城市的最小费用
   //建立一个顶点三元组堆（索引，费用，到达时间）按照费用从小到大排序，对于费用最小的tuple，pop后，遍历所有的航班，如果出发时间大于这个tuple的到达时间，则将其加入队列，否则continue；
   //更新cost【id】、数组大小，取最小值，
    int c_size = citys.size();
        QVector<Tinfo *>res;//保存路径
        QVector<int> cost (20*c_size,INF);//花费
        QVector<date> ti (20*c_size,date(INF,INF));
        QVector<Tinfo *> pre (20*c_size,nullptr);
        priority_queue<tp>pq;
        int b_id = find(b);
        int l_id = find(l);
        * ans2 = date(0,0);
        * ans = 0;
        if(b_id == -1 || l_id == -1){/*信息不存在*/return res;}
        pq.push(tp(0,b_id,date(0,0)));//初始化起点
        while(!pq.empty())
        {
            tp f = pq.top();
            pq.pop();
            city & p = citys[f.id];
            //查找所有路线进行更新，需要在city中实现
            date check = (f.t==date(0,0))?date(0,0):date(f.t.hour+(int)type+1,f.t.minute);
            QVector<Tinfo *>tmp = p.timeinfo(check,type);
            for(auto i : tmp)
            {
                //进队
                QString e_name = i->e->getname();
                int index = find(e_name);
                if(f.cost + i->cost < cost[index])
                {
                    cost[index] = f.cost + i->cost;
                    pre[index] = i;
                }
                //所有的都要进队
                pq.push(tp(f.cost + i->cost,index , i->l));
            }
        }
        //处理答案
        if(cost[l_id]==INF)/*不存在路径*/return res;
        * ans2 = * ans2 + pre[l_id]->l;
        for(int i = l_id;i != b_id ;i = find(pre[i]->f->getname())/*转移过来的路径的起点，也就是前驱城市*/)
        {
            res.push_front(pre[i]);
            if(pre[i]->f->getname()==citys[b_id].getname())
            {
                * ans2 = * ans2 - pre[i]->b;//统计起始时间和终止时间

            }
        }//前驱
        //费用答案
        * ans = cost[l_id];
        //时间答案
        return res;
}//核心算法1,最小费用，

QVector<Tinfo *> Graph::solution2(bool type,QString b,QString l,date  * ans,int * ans2)
{
    vector<int>v;
    //遍历
    * ans2 = 0;
    //int csize = citys.size();
    QVector<Tinfo *>res;//记录路径结果
    QMap<QString,Tinfo *>aft;
    QMap<QString,date>tmp_cost;
    int root = find(b);int e = find(l);
    if(root== -1||e== -1){/*错误*/return res;}
    date j = citys[root].dfs(date(0,0),&citys[root],&citys[e],type,aft,tmp_cost,date(0,0));//搜索的答案
    * ans = j;
    //如果j为INF说明答案不存在
    if(j == date(INF,INF))return res;
    //传入参数mp，返回来记录答案,包含起点和终点
    QString t = citys[root].getname();
    for(QString i = t ;i != l; i= aft[i]->e->getname())//是向后寻找的
    {
        res.push_back(aft[i]);
        * ans2 += aft[i]->cost;
    }
    //找出最短时间对应的费用
    return res;
}
//核心算法2,最短时间
